\section{Introduction}
\label{sec:intro}

An essential quality of a planner is its modeling capability. It
has been a continuing endeavor to expand the modeling capability of
planning formulations. An important development beyond
classical planning is temporal planning, which deals with
durative actions occurring over extended intervals of time~\cite{Penber94}. 
Particularly, both preconditions and effects of durative actions can be temporally
quantified. Several temporal planning algorithms
have been developed, including~ZENO~\cite{Penber94},
TMP~\cite{Smith99}, TLPlan~\cite{Bacchus01}, TP4~\cite{Haslum01},
LPG~\cite{Gerevi02}, TALPlanner~\cite{Kvarnstrom03},
VHPOP~\cite{Younes03}, SGPlan~\cite{Wah06}, LPG-td~\cite{Gerevini08}, TFD~\cite{Eyerich09} and a concurrency version of LPG (LPG-c)~\cite{Gerevini10}. 
These planners have been successfully applied to many planning problems.

Despite their success on many planning problems, these
planners are restrained by two limitations. First, most existing
temporal planners cannot deal with temporally expressive problems.
Temporal action concurrency was first introduced in PDDL2.1~\cite{PDDL21}.
Cushing~\cite{Cushing07} first presented the notion of temporal expressiveness.
%was discussed in~\cite{Cushing07}. 
A planning problem is temporally expressive if all of its solutions require action concurrency,
which indicates that one action occurs within the time interval of another action. 
Most existing temporal planners are temporally simple without requiring action concurrency~\cite{Cushing07}. 
Second, most existing temporal planners either attempt to minimize
the total duration of the solution plan (i.e. makespan), or do not
consider any quality metric at all. However, for many %real-world
applications, it is required to optimize not only the
makespan, but also the total sum of the action costs~\cite{Do03},
which can represent many quantities, such as the cost of resources used, the total money spent, or the total energy consumed. 
Action cost was introduced as a new criterion in IPC-6 planning competition~\cite{IPC6}.

%R.Huang
%Why required concurrency is a language?? doesn't make sense at all;
%It's the original description in Cushing07.
\nop{ Required concurrency, which has the ability of encoding
problems for which all solutions are concurrent, divides temporal
languages into temporally expressive~(required concurrency) and
temporally simple. We denote these temporal planning problems, which
require concurrency actions as well as actions consuming cost, as
cost sensitive temporally expressive~(CSTE) planning problems.}




\nop{ Many real-world planning problems are inherently temporal and
contain more intrinsically concurrent actions than what we have
assumed before.  The high concurrency of actions has not been
sufficiently exploited in most existing planning systems.
Furthermore, total action costs, another important metric in planning
 problems, is usually studied in classical planning contexts only.
In many real situations of temporal planning, it is also desirable
to optimize total action costs. We propose to use SAT based
approaches for optimal temporally expressive planning. The resulting
planner will find the plan that has the optimal number of makespan,
along with minimal total action costs.


On the other hand, the latest results have shown that a large class
of temporal planning problems, the temporally expressive problems,
have not been adequately studied~\cite{Cushing07,Cushing07:ICAPS}.
This is in part due to the lack of a sufficient number of benchmarks
that are truly temporally expressive and representative of
real-world problems. The lack of sufficient temporally expressive
domains is also a barricade to future advances in temporal planning.
We will study a real-world case, Peer-to-Peer networks, where both
temporally expressiveness and total action costs are of our greatest
interests. }


Both required concurrency and action costs are important for
modeling %real-world 
planning problems. In this paper, we propose a
general planning paradigm, called cost-sensitive temporally
expressive (CSTE) planning. A CSTE planning problem is a temporally
expressive problem in which actions are associated with costs. 
%with multiple objectives such as the shortest makespan and a minimal total cost. 
Although CSTE planning problems are complex and difficult to solve, they are important and
ubiquitous in many applications.
%the real world. 
Example CSTE domains include:

\begin{enumerate}

%a little confusing of why need concurrency in p2p.
\item \textbf{Peer-to-Peer network communication.}
In Peer-to-Peer network communication, one peer's uploading has to
be concurrent with one or more other peers' downloading. Besides the
required concurrency, modern communication is service oriented;
communication actions are charged by different costs,
depending on the types of network service used. A desirable planner
will need to find temporally expressive solutions that also minimize
the total action costs and thus require a CSTE planning.

\item \textbf{Web service composition.}
Web service composition (WSC) is the problem of integrating multiple
web services to satisfy a particular request~\cite{Rao04}. Planning has
been adopted as one of the major methods for WSC~\cite{Carman03,Rao04}. 
%Real-world 
WSC problems may require CSTE planning, since different web services operate under
different conditions and different rates of cost (some are free).
As a result, it is desirable to optimize the QoS metrics, such as total price, reliability, and reputation.
Moreover, temporally concurrent actions are often needed to coordinate multiple web services. 
%For example,
%. due to the time limit of a banking service session.

\nop{ When casting WSC as planning problem, action cost is by all
means important as well, for services may have different charging
costs.
%Besides action cost, most existing works focus on addressing the
%uncertainties~\cite{Hoffmann:jair2009}, the nature of any practical
%WSC application. Nevertheless, uncertainty is not the unique issue
%in WSC. Although so far mentioned by little literature,}
Although so far been mentioned by little literature, durative action
may be just as important as action cost. Consider a case we want to
use some services, which depend on online bank services. The banking
services, for either security or network traffic reason, are of
limited time sessions; the connections will be dropped by the banks'
servers when the session is expired.}

\item \textbf{Autonomous systems.}
Planning for autonomous systems, including robotics, rovers, and
spacecrafts, often requires CSTE planning. Consider a spacecraft
controlling example~\cite{smith:jair03} in which the spacecraft movement is made by firing
thrusters. Multiple operations need to be performed within the time
interval when the thrusters are fired, thus requiring action concurrency.
Moreover, operation costs such as energy need to be minimized in
order to best utilize the on-board resources. \nop{In fact, this
category of scenario might be so complicated (w.r.t. concurrencies)
such that, current PDDL2.1~\cite{fox:jair03} based temporally
expressive planing, even in its richest form, cannot completely
handle what the system really needs.}


\nop{Some early studies showed that, modern search based
propositional planning methods had already been efficient enough to
be used in manufacturing real time systems~\cite{do:icaps2008}.}

\item \textbf{Real time manufacturing system.}
In real time manufacturing systems~\cite{do:icaps2008}, action
concurrency is often mandatory. For instance, in %a machine shop
baking ceramics~\cite{Cushing07:ICAPS}, the kilning and baking
actions need to be executed simultaneously, in which kilning has to
be executed within the time interval of baking. Moreover, to produce
more products with less time and materials, one needs to optimize the
arrangement of concurrent actions to achieve shorter makespans and
less total action costs.

\end{enumerate}
%\end{itemize}

\nop{ For most CSTE problems, it could be, arguably, possible to
split the durative action into consecutive simpler actions,
mimicking the concurrencies. However, essentially}


\nop{ The goal of this paper is to develop an efficient SAT-based
approach that can find plans with the \emph{minimum total action
costs}. A general framework we propose for achieving this goal is to
optimally solve the SAT instance with respect to the given
preference for each makespan $k$ and keep increasing $k$ until we
achieve a certain stop condition that guarantees the overall
optimality. We name the above framework SAT-SCAN.

The main difficulty of the SAT-SCAN framework is its time
complexity. First, for each makespan, unlike SATPlan that only needs
to find \emph{any} satisfiable solution, we need to do a complete
search to find the optimal solution with the best preference score.
Second, while extending $k$ to only the first satisfiable level
finds a plan with the shortest makespan, it generally cannot
guarantee optimizing other preferences. We may need to extend $k$ to
many more levels after the first satisfiable level, which is
expensive.


In order to address the above difficulties and develop a practical
algorithm, we identify a number of key issues for the efficiency of
the framework and propose strategies to address each of them. These
strategies bring significant changes to the original SATPlan and
make the system much more efficient for the new optimization
paradigm. We list those main contributions as follows. }

%\subsection{A CSTE planning framework}

Currently, very few existing automated planner can handle CSTE problems. There are
only a few temporally expressive planners, such as
TM-LPSAT~\cite{Shin:aaai04}, Crikey2~\cite{Coles08},
Crikey3~\cite{Coles08:AIJ}, LPG-c~\cite{Gerevini10}, and TFD~\cite{Eyerich09}. 
But most of them only optimize temporal makespan.
%There is a lack of method for CSTE planning.
%The SAT-based approaches have been widely adopted in planning~\cite{Kautz92,Kautz:IPC-04}. 
%In addition to STRIPS planning, 
%SAT-based planning methods have been extended to dealing with complex planning domains such as numerical
%planning and temporal planning~\cite{Giunchiglia07,Mattm07,Pham08:AIJ}. 

In this paper, we introduce an efficient CSTE planing framework based
on a Satisfiability (SAT) transformation, as shown in 
Figure~\ref{fig:scop}. Central to this approach is a 
transformation for turning a CSTE instance into an optimization
problem with SAT-based constraints~(which is called a MinCost SAT
formulation). Specifically, MinCost SAT is a SAT problem with an objective 
of minimizing the total cost of literals assigned to be true~\cite{Li04}.
We develop BB-DPLL, a branch-and-bound algorithm based on the DPLL procedure~\cite{zhang:CAV-02}, to directly solve MinCost SAT problems. 
%The core of our algorithm is effective bounding and pruning techniques that derives tight lower bounds of search by
%exploiting the structures of a CSTE problem. 
%We also propose an action-cost-based variable branching scheme to further improve search efficiency.
We also propose an effective bounding technique that derives tight lower bounds of search by exploiting the structures of a CSTE problem, and an action-cost-based variable branching scheme to further improve search efficiency.


\nop{
\begin{itemize}

\item We develop a SAT-based framework for CSTE planning, as shown in
Figure~\ref{fig:scop}. Central to this approach is a 
transformation for turning a CSTE instance into an optimization
problem with SAT-based constraints~(which is called a MinCost SAT
formulation). Specifically, MinCost SAT is a SAT problem with an objective 
of minimizing the total cost of literals assigned to be true~\cite{Li04}.

\nop{
\item We propose a new approach to solving MinCost SAT problems
by translating them into weighted partial Max-SAT problems and
solving them using a Max-SAT solver. Weighted partial Max-SAT is an
important variation of the general SAT problem that has weighted
soft and hard constraints. The objective is to find a variable
assignment that satisfies all hard constraints and maximizes
the total weight of soft constraints~\cite{Fu06b}.
}

\item We develop BB-DPLL, a branch-and-bound algorithm based
on the DPLL procedure~\cite{zhang:CAV-02}, to directly solve MinCost
SAT problems. At the core of our algorithm is an effective
estimation function that derives tight lower bounds of search by
exploiting the structures of a CSTE problem. We also propose an action-cost-based variable branching scheme to further improve
search efficiency.

\item We compose a library of CSTE planning domains based on currently
available temporally expressive planning domains. Further, we create
a new CSTE planning domain that models a peer-to-peer (P2P)
network communication control problem. The current research on
temporal planning has been hindered by the lack of a sufficient
number of benchmarks that are truly temporally expressive and
representative of real-world problems~\cite{Cushing07:ICAPS}. 
Our work may help address this issue.
\end{itemize}
}

\nop{ Two different MinCost SAT solving strategies are used in our
investigation. The first one is to use a generic modern Max-SAT
solver; we convert the MinCost SAT formulas into weighted partial
Max-SAT formulas, then apply state-of-the-art Max-SAT solvers. }


\nop{ In this paper, we present $SCOP$, a SAT-based planner that can
handle both temporally expressiveness and action cost.   Then, based
on this framework, we study several different problem solving
techniques to make our solver find minimal total cost more
efficiently. Finally, we show the advantages of our proposed solver
over existing temporally expressive planners using experimental
results.}

\nop{ Our experimental results show that, this framework has
advantages in terms of both solution quality and solving time, if
compared with existing temporally expressive planners. }

\begin{figure}%[tp]
 \centering
\scalebox{0.7}{\includegraphics{./figure/SCOP-c.eps}}
\parbox{5in}{
\caption{\label{fig:scop}\small  The architecture of our CSTE
planner.}}
\end{figure}

The resulting CSTE planner not only handles temporal
expressiveness efficiently, but also optimizes the makespan and minimizes total action costs.
%multiple objectives including the makespan and total action costs. 
We first propose a SAT-based framework for CSTE planning by taking advantage of the planning
as satisfiability method to optimize makespan. Then, for any given
makespan, our solver is able to find a plan with the minimum total
action costs. Figure~\ref{fig:scop} shows the architecture of our
CSTE planner. Our results show great potentials of this framework.
In particular, our results show that our SAT-based approach is
currently a good choice for CSTE planning, especially when
the problems are highly concurrent. 
The solution strategy that we proposed solves the problem efficiently,
comparing favorably against other existing temporally expressive planners.

\nop{In addition, our BB-DPLL algorithm can significantly improve
the solution quality using a reasonable amount of time.}


\nop{ SATPlan~\cite{Kautz:IPC-04}~\cite{Kautz06} is a representative
planner under the paradigm of planning as
satisfiability~\cite{Kautz92}. Given a planning problem, SATPlan
iteratively increments an integer $k$, the makespan of the solution.
For each $k$, SATPlan converts the planning graph with $k$ levels
into a SAT formulation and uses a complete SAT solver to solve the
SAT instance. If the SAT instance is satisfiable, SATPlan will stop
and return a solution. Otherwise, SATPlan will increase $k$ by one
and keep searching.

SATPlan optimizes the makespan of the solution, which comes for free
with the structure of its search algorithm. SATPlan is also
relatively efficient comparing with other optimal planners (although
with different optimality criteria) since it leverages on the
long-time development of highly efficient SAT solvers. However, a
disadvantage of SATPlan is that it cannot optimize preferences other
than the makespan. As preferences are becoming a highly demanded
feature of planning, such a disadvantage of SATPlan seriously limits
its applicability. }

\vspace{+0.2in}

The rest of this paper is organized as follows.  In
Section~\ref{sec:background}, we define cost sensitive temporally
expressive (CSTE) planning.
We present the SAT-based CSTE planning framework
%, including the MinCost SAT encoding 
in Section~\ref{sec:encoding}.
In Section~\ref{sec:opt}, we present our BB-DPLL algorithm enhanced with bounding and variable branching mechanisms for solving encoded MinCost SAT problems. 
%In Section~\ref{sec:P2P}, as a case study for CSTE planning, we develop a CSTE domain for optimizing P2P network communications.
%We discuss the high concurrencies in CSTE domains in Section~\ref{concurrency}.
We present our experimental results in 
%the P2P network domain and several other 
a variety of CSTE planning domains in Section~\ref{sec:experiments}. We discuss related work in
Section~\ref{sec:related} and conclude in Section~\ref{sec:discussions}.


%Some early work and results appeared in~\cite{huang09:ICAPS}.

